package com.skh.array;

import cn.hutool.core.bean.BeanUtil;

import java.util.Arrays;

/**
 * @Author: skh
 * @Date: 2020/3/3 11:01
 * @Description:  最短无序连续子数组
 */
public class FindUnsortedSubarray {

    /**
     * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
     *
     * 你找到的子数组应是最短的，请输出它的长度。
     *
     * 示例 1:
     *
     * 输入: [2, 6, 4, 8, 10, 9, 15]
     * 输出: 5
     * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
     *
     */

    /**
     * 思路:先给数组升序排序，然后按位置和原数组比较。记录第一个和最后一个不一样的数的坐标.
     * 最后一个不一样的数减第一个不一样的数，再加一就是需要修改的元素个数。
     */
    public int findUnsortedSubarray(int[] nums) {

        int start = 0;
        int end = 0;
        int count = 0;

        if (nums.length == 0) {
            return 0;
        }

        int[] newNums = Arrays.copyOf(nums, nums.length);

        Arrays.sort(newNums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != newNums[i]) {
                count+=1;
                end = i;
                if (count == 1) {
                    start = i;
                }
            }
        }

        return count==0?0:end-start+1;
    }
}
